//
// Created by 12967 on 2022/1/20.
//

#ifndef DATASTRUCTURE_AVLTREE_H
#define DATASTRUCTURE_AVLTREE_H
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include "fileNode.h"


using namespace std;

struct treeNode{
    treeNode* left=NULL;
    treeNode* right=NULL;
    string word;
    FileListNode* files=NULL;
    int height=0;
    int balanceFactor=0;
};

extern int height(treeNode*);
extern int factor(treeNode*);
extern void clear(treeNode*);
extern long scan(treeNode*);

class AVLtree {

public:
    AVLtree(){
        this->root=NULL;
    };

    void insert(const string& word,const string& fileName){
        if(root==NULL){
            root=new treeNode;
            root->word=word;
            root->files=new FileListNode;
            root->files->file=fileName;
        }else{
            treeNode* p=root;
            treeNode* pp=root;
            treeNode* upp=root;
            treeNode* mark=root;
            treeNode* markp=root;
            bool isleft=true;
            while(p!=NULL){
                upp=pp;
                pp=p;
                int def=word.compare(p->word);

                if(def==0){
                    FileListNode* fileIterator=p->files;
                    FileListNode* par;
                    while(fileIterator!=NULL){
                        if(fileIterator->file==fileName){
                            return;
                        }else{
                            par=fileIterator;
                            fileIterator=fileIterator->nextFile;
                        }
                    }if(p->files==NULL){
                        p->files=new FileListNode;
                        p->files->file=fileName;
                    }else{
                        fileIterator=new FileListNode;
                        fileIterator->file=fileName;
                        par->nextFile=fileIterator;
                    }
                }else{
                    if(def==-1){
                        p=p->left;
                        if(pp->balanceFactor==1){
                            mark=pp;
                            markp=upp;
                            if(markp->left==mark){
                                isleft=true;
                            }else{
                                isleft=false;
                            }
                        }
                        if(p==NULL){
                            p=new treeNode;
                            p->word=word;
                            p->files=new FileListNode;
                            p->files->file=fileName;
                            pp->left=p;
                            if(pp->right==NULL)
                                pp->balanceFactor=1;
                            else
                                pp->balanceFactor=0;
                            if(mark->left!=NULL&&mark->left->balanceFactor==1&&pp->balanceFactor!=0){
                                treeNode* mrkLeft=mark->left;
                                if(mrkLeft->balanceFactor==1){
                                   mark->left=mrkLeft->right;
                                   mrkLeft->right=mark;
                                   mark->balanceFactor=0;
                                   mrkLeft->balanceFactor=0;
                                    if(markp==root){
                                        root=mrkLeft;
                                        return;
                                    }
                                   if(isleft)
                                       markp->left=mrkLeft;
                                   else
                                       markp->right=mrkLeft;
                                }else{
                                    treeNode* mklrChild=mrkLeft->right;
                                    mrkLeft->right=mklrChild->left;
                                    mark->left=mklrChild->right;
                                    mklrChild->left=mrkLeft;
                                    mklrChild->right=mark;
                                    if(mklrChild->balanceFactor==0)
                                    {
                                        mrkLeft->balanceFactor=0;
                                        mark->balanceFactor=0;
                                    }else if(mklrChild->balanceFactor==1){
                                        mrkLeft->balanceFactor=0;
                                        mark->balanceFactor=-1;
                                    }else{
                                        mrkLeft->balanceFactor=1;
                                        mark->balanceFactor=0;
                                    }
                                    mklrChild->balanceFactor=0;
                                    if(isleft)
                                        markp->left=mklrChild;
                                    else
                                        markp->right=mklrChild;
                                }
                            }
                            return;
                        }
                    }else{
                        if(def==1){
                            p=p->right;
                            if(pp->balanceFactor==-1){
                                mark=pp;
                                markp=upp;
                                if(markp->left==mark){
                                    isleft=true;
                                }else{
                                    isleft=false;
                                }
                            }

                            if(p==NULL){
                                p=new treeNode;
                                p->word=word;
                                p->files=new FileListNode;
                                p->files->file=fileName;
                                pp->right=p;
                                if(pp->left==NULL)
                                    pp->balanceFactor=-1;
                                else
                                    pp->balanceFactor=0;
                                if(mark->right!=NULL&&mark->right->balanceFactor==-1&&pp->balanceFactor!=0){
                                    treeNode* mrkRight=mark->right;
                                    if(mrkRight->balanceFactor==-1){
                                        mark->right=mrkRight->left;
                                        mrkRight->left=mark;
                                        mark->balanceFactor=0;
                                        mrkRight->balanceFactor=0;
                                        if(markp==root){
                                            root=mrkRight;
                                            return;
                                        }
                                        if(isleft)
                                            markp->left=mrkRight;
                                        else
                                            markp->right=mrkRight;
                                    }else{
                                        treeNode* mkrlChild=mrkRight->left;
                                        mark->right=mkrlChild->left;
                                        mrkRight->left=mkrlChild->right;
                                        mkrlChild->left=mark;
                                        mkrlChild->right=mrkRight;
                                        if(mkrlChild->balanceFactor==0){
                                            mark->balanceFactor=0;
                                            mrkRight->balanceFactor=0;
                                        }else if(mkrlChild->balanceFactor==-1){
                                            mrkRight->balanceFactor=0;
                                            mark->balanceFactor=1;
                                        }else{
                                            mrkRight->balanceFactor=-1;
                                            mark->balanceFactor=0;
                                        }
                                        if(markp==root){
                                            root=mkrlChild;
                                            return;
                                        }
                                        if(isleft)
                                            markp->left=mkrlChild;
                                        else
                                            markp->right=mkrlChild;
                                    }
                                }
                                return;
                            }
                        }
                    }
                }
            }
        }
    }

    void search(const string& targetWord,vector<string>& files,int* biop){
        for(int i=0;i<files.size();i++){
            biop[i]=0;
        }
        treeNode* pointer=this->root;
        while(true){
            if(pointer==NULL){
                cout<<"NO MATCHED FILES!"<<endl;
                return;
            }
            int def=targetWord.compare(pointer->word);
            if(def==0){
                FileListNode* fileIterator=pointer->files;
                while(fileIterator){
                    auto iter=find(files.begin(),files.end(),fileIterator->file);
                    auto index=std::distance(files.begin(),iter);
                    biop[index]=1;
                    fileIterator=fileIterator->nextFile;
                }
                cout<<endl;
                return;
            }else{
                if(def<0){
                    pointer=pointer->left;
                }else{
                    pointer=pointer->right;
                }
            }
        }
    }

    void mutiSearch(vector<string> files){
        auto* command=new queue<string>;
        string s;
        while(cin>>s){
            if(s==",")
                break;
            command->push(s);
        }
        cout<<"WAIT A SEC......"<<endl;
        clock_t start,end;
        start=clock();
        int* result=new int[files.size()];
        this->search(command->front(),files,result);
        command->pop();
        while(!command->empty()){
            bool isOr=true;
            string op=command->front();
            if(op=="AND")
                isOr=false;
            command->pop();
            if(command->empty())
            {
                cout<<"SYNTAX ERROR!!!"<<endl;
                return;
            }else{
                int* result2=new int[files.size()];
                this->search(command->front(),files,result2);
                command->pop();
                if(isOr){
                    for(int i=0;i<files.size();i++){
                        result[i]=result[i]|result2[i];
                    }
                }else{
                    for(int i=0;i<files.size();i++){
                        result[i]=result[i]&result2[i];
                    }
                }

            }
        }
        bool noselected=true;
        cout<<"THE FINAL RESULT IS: "<<endl;
        for(int i=0;i<files.size();i++){
            if(result[i]){
                noselected=false;
                cout<<files[i]<<"\n";
            }

        }
        if(noselected)
            cout<<"NO MATCHED FILES!!!";
        cout<<endl;

        end=clock();
        auto time=(double)(end-start)/CLOCKS_PER_SEC*1000;
        cout<<"Total time:"<<time<<"ms"<<endl;
    }


    treeNode* root;
};



#endif //DATASTRUCTURE_AVLTREE_H
